package Medium;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LC2542 {
    /**
     * 第三方题解。这个问题可以通过适当地转化来“剪枝”，或降低复杂度。将nums1和nums2一起排序，排序的依据是nums2需要从大到小，
     * 新的序列记为sortedNums1和sortedNums2。维护一个小根堆，记录sortedNums1已考察范围内最大的k个元素。对于任意的i>=k，
     * 考虑sortedNums2[i]作为新的最小值，那么选定的k个数字必定从sortedNums1[0~i]和sortedNums2[0~i]中产生。由于存在小根堆，
     * 此时只要考查sortedNums1[i]是否能使堆中数字变大即可。
     * 启示：有序是很好的性质。
     * 时间复杂度：NlogN
     */
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;
        Integer[] idxMap = new Integer[n]; // 映射到原数组中的索引
        for (int i = 0; i < n; i++) idxMap[i] = i;
        Arrays.sort(idxMap, (i, j) -> nums2[j] - nums2[i]); // 实现从大到小排序
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        double sum = 0, maxScore;
        for (int i = 0; i < k; i++) {
            heap.offer(nums1[idxMap[i]]);
            sum += nums1[idxMap[i]];
        }
        maxScore = nums2[idxMap[k - 1]] * sum;

        for (int i = k; i < n; i++) {
            int nums1NewValue = nums1[idxMap[i]], nums2NewValue = nums2[idxMap[i]];
            // 堆始终保存了nums1已考察范围内的k个最大值，如果新加入的值不是更大，则可以跳过后续操作（maxScore也不可能更新）
            if (nums1NewValue < heap.peek()) continue;
            sum -= heap.poll();
            sum += nums1NewValue;
            heap.offer(nums1NewValue);
            double score = nums2NewValue * sum;
            if (score > maxScore) maxScore = score;
        }

        return (long) maxScore;
    }
}
